% !TEX encoding = UTF-8 Unicode
\chapter*{Introducci\'on}
\addcontentsline{toc}{chapter}{Introducci\'on}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE,RO]{\bfseries\thepage}
\fancyhead[LO]{\bfseries Introducci\'on}
\fancyhead[RE]{\bfseries Introducci\'on}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
En este trabajo estudiaremos variantes de un problema clásico en geometría computacional llamado el problema de \emph{Ubicación de servicios}.
En dicho problema se tiene un conjunto de clientes que demandan un servicio (gasolineras, hospitales, tiendas, cobertura telefónica, cobertura televisiva, etc.);
dicho servicio se ofrece a través de un conjunto de proveedores que deberán estar situados de manera que todos los clientes tengan acceso al servicio.
Existen muchas variantes del problema, sin embargo, la más estudiada es aquella relacionada con encontrar la ubicación óptima para los proveedores, 
de modo que minimicemos la distancia máxima entre un cliente y su proveedor más cercano.

A lo largo de este trabajo nos enfocaremos en servicios de comunicación inalámbrica y particularmente, pensaremos a nuestros proveedores como un conjunto de antenas capaces de emitir mensajes a un conjunto de clientes con una potencia dada. 
Este modelo puede ser comparado con el servicio de radio o televisión, el cual se ofrece a través de antenas retransmisoras ubicadas en distintos puntos de una ciudad, y que cuentan con un cierto radio de influencia alrededor de la antena; ver Figura~\ref{fig:AntenasTelevision}.

\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.85\textwidth]{img/intro/AntenasTelevision.pdf}
\caption{\small Un conjunto de antenas retransmisoras de televisión ofreciendo su servicio a un conjunto de clientes.}
\label{fig:AntenasTelevision}
\end{center}
\end{figure}

Este modelo supone que los clientes son únicamente receptores y el objetivo es que cada uno reciba el mensaje de al menos una de las antenas emisoras.
El proceso de comunicación que estudiaremos es unidireccional y el objetivo es optimizar la potencia de transmisión de las antenas, ya que las antenas más potentes son más caras y requieren de mayor energía para transmitir.

El modelo se describe formalmente a continuación.
Una antena inalámbrica $\mathcal A$ tendrá asignada una posición y 
una potencia de transmisión que definirá un radio de cobertura $r$ alrededor de dicha antena, 
de tal forma que un receptor $\mathcal R$ escucha el mensaje emitido por $\mathcal A$, 
si y sólo si $\mathcal R$ se encuentra a distancia a lo más $r$ de $\mathcal A$.

Geométricamente, una antena inalámbrica $\mathcal A$ es modelada por un círculo $C$, centrado en la posición de la antena y con un radio $r$ definido por la potencia de $\mathcal A$. 
Un receptor $\mathcal R$, generalmente será representado por un punto, de modo que para que $\mathcal R$ reciba el mensaje emitido por $\mathcal A$, el punto que lo representa deberá estar dentro del círculo $C$. Diremos que un receptor $\mathcal R$ tiene cobertura, si existe al menos una antena $\mathcal A$ tal que $\mathcal R$ recibe los mensajes emitidos por $\mathcal A$.

\subsection*{El problema del $k$-centro}

Una vez descrito el modelo, pasaremos a describir el problema de optimización que estudiaremos, 
dicho problema es conocido como el problema del $k$-centro y se plantea de la siguiente manera: 

Dados $P$ un conjunto de $n$ puntos en el plano representando a los receptores y $k$ un entero positivo, 
un $k$-centro de $P$ es un conjunto $A$ de $k$ puntos en el plano representando a las antenas, de tal forma que la distancia máxima entre un receptor de $P$ y su antena más cercana sea la menor posible.

Sea $A$ un $k$-centro de $P$ y sea $r$ la distancia máxima entre un receptor y su antena más cercana. 
Note que si pedimos que todas las antenas tengan la misma potencia, 
entonces el radio mínimo que una antena necesita cubrir es $r$, ya que de lo contrario, sin importar donde coloquemos las $k$ antenas, un receptor de $P$ quedaría siempre sin cobertura.
Es por esto que la solución al problema de optimización está dada por un $k$-centro $A$ y la distancia $r$ asociada a éste, es decir, que buscamos la menor potencia posible que podemos asignar a $k$ antenas, de manera que, distribuidas de manera óptima en el plano, ofrezcan cobertura a todos los clientes.

El problema del $k$-centro ha sido estudiado extensamente, Megiddo y Supowit probaron que el problema es NP-completo~\cite{Megiddo84onthe}, más aún, Feder y Greene probaron que es NP-completo aproximarlo por un factor menor a 1.82~\cite{OptimalAlgorithmsForApproximateClustering}.
Sin embargo, existen varios algoritmos con factor de aproximación 2 y uno de ellos puede ser encontrado en~\cite{Gonzalez1991181}.
Por otra parte, el problema del $k$-centro discreto, en el cual un conjunto $M$ de posibles ubicaciones para las antenas está dado desde un inicio, es también NP-completo~\cite{OptimalPackingAndCovering}, no obstante es $1+\varepsilon$ aproximable para cualquier $\varepsilon > 0$~\cite{GeometricClusteringToMinimizeSum}.
Note que si $k$ es constante con respecto a $n$, entonces el problema del $k$-centro discreto se puede resolver en tiempo polinomial, revisando los $O(n^k)$ posibles subconjuntos de $k$ elementos de $M$ y determinando cual es el óptimo.
Para el caso cuando $k=2$, existe un algoritmo determinista de complejidad $O(n \log ^2 n \log^2\log n)$ para el problema del 2-centro~\cite{Chan:1999:MPT:326180.326185}, dicho algoritmo es comparable con el algoritmo aleatorio para el mismo problema propuesto por Eppstein en~\cite{Eppstein:1997:FCP:314161.314198}, el cual tiene un tiempo esperado de ejecución de $O(n\log ^2 n)$.
Vale la pena resaltar que el caso $k=2$, es el único caso en que se conocen algoritmos para resolver el problema del $k$-centro en menos de $O(n^k)$.

Para el caso $k=1$, el problema del $k$-centro es equivalente a encontrar el círculo de radio mínimo que contenga a todos los receptores de $P$, visto de otra forma, se busca encontrar la posición de la antena en el plano
que requiera la menor potencia para cubrir a todos los elementos de $P$. 

El problema de encontrar el círculo de radio mínimo que contiene a un conjunto $P$ de $n$ puntos dados fue propuesto originalmente por Sylvester en 1857~\cite{Sylvester1857}. 
Por simplicidad llamaremos $P$-círculo a cualquier círculo que contenga al conjunto $P$.
Un algoritmo de $O(n^2)$ fue presentado por Elzinga y Hearn~\cite{Elzinga01111972} para encontrar el $P$-círculo de radio mínimo. 
Más adelante, Preparata~\cite{PreparataMinimumSpanningCircle} y Shamos y Hoey~\cite{ShamosClosestPointProblems} presentaron independientemente dos algoritmos para resolver el problema en tiempo $O(n\log n)$. 
Lee~\cite{LeeFarthestVoronoi} propuso el diagrama de Voronoi del punto más lejano, con el cual también fue posible encontrar el centro del $P$-círculo de radio mínimo en tiempo $O(n\log n)$.
Finalmente, Megiddo~\cite{LinearTimeAlgorithmsForLinearProgramming} propuso un algoritmo óptimo de tiempo $O(n)$ para resolver el problema del 1-centro en el plano utilizando ``prune and search''. Más aún, el problema del 1-centro se puede resolver en tiempo $O(n)$ en el peor caso en cualquier dimensión fija $d$~\cite{ChazelleDeterministicAlgorithms}\cite{DyerMultidimensionalSearch}.
Sin embargo debido a la complejidad de la implementación de dichos algoritmos, varios algoritmos aleatorios de fácil implementación fueron propuestos posteriormente con un tiempo de ejecución esperado de $O(n)$~\cite{Clarkson:1995:LVA:201019.201036}\cite{WelzEmoSmallestEnclosingDisks}.

Nuevas variantes del problema del 1-centro se han presentado recientemente, en este trabajo nos enfocaremos en aquellas en las que se busca encontrar el centro del $P$-círculo de radio mínimo bajo ciertas restricciones geométricas. Algunas de estas variantes se presentan a continuación:

Megiddo estudió el problema de encontrar el $P$-círculo de radio mínimo cuyo centro debe pertenecer a una línea recta dada, y propuso un algoritmo óptimo de tiempo $O(n)$~\cite{LinearTimeAlgorithmsForLinearProgramming} para resolver el problema.
Hurtado, Sacristan y Toussaint presentaron un algoritmo de tiempo $O(n+m)$ para encontrar el $P$-círculo de radio mínimo cuyo centro está restringido a cumplir $m$ desigualdades lineales~\cite{HurtadoConstrainedMinMax}. En particular, esto resuelve el problema el $P$-círculo de radio mínimo con centro en un polígono convexo de tamaño $m$.
Bose y Toussaint consideraron la generalización de este problema, restringiendo el centro del $P$-círculo al interior de un polígono simple de tamaño $m$. 
Ellos propusieron un algoritmo de tiempo $O((n+m)\log (n+m) + k)$, dónde $k$ es el número de intersecciones del polígono con el diagrama de Voronoi del punto más lejano de $P$~\cite{BoseToussaint1996}.

Posteriormente, Das, Karmakar, Nandy y Roy propusieron el problema de consulta, en el cual se permite preprocesar al conjunto $P$ en un a estructura de datos, de modo que pueda responder a consultas de la siguiente forma:
Dada una línea recta $L$, encontrar el círculo de radio mínimo con centro en $L$ de manera eficiente.
Ellos presentaron un algoritmo con tiempo de preprocesado $O(n\log n)$, espacio lineal y que responde a las consultas en tiempo $O(\log ^2 n)$~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}.
Posteriormente Das, Karmakar y Roy mejoraron el tiempo de la consulta a $O(\log n)$ utilizando espacio y preprocesado $O(n^2)$~\cite{FastEnclosingCircle}.
En este trabajo estudiamos el mismo problema y presentamos un algoritmo óptimo.
En dicho algoritmo proponemos un preprocesado de tiempo $O(n\log n)$ utilizando espacio lineal, que permite responder a las consultas en tiempo $O(\log n)$.
Aunque cabe mencionar que Bose, Langerman y Roy propusieron otro algoritmo y estructura de datos completamente distintos que alcanzan el mismo tiempo de preprocesado y de consulta~\cite{SmallestEnclosingCircleWithCenterOnQueryLine}.


\subsection*{Separación por círculos}
El segundo problema que trataremos en este trabajo esta relacionado con el concepto de separación geométrica.
Formalmente definimos $\Phi$ como una familia de curvas en el plano tal que, para cada $\phi\in \Phi$, $\mathbb{R}^2-\phi$ tiene exactamente dos componentes conexas $\Pi_1(\phi), \Pi_2(\phi)$.
Decimos entonces que dos subconjuntos $P,Q$ de $\mathbb{R}^2$ son separables por $\Phi$, si y sólo si existe un $\phi \in \Phi$, tal que el interior de $P$ está contenido en $\Pi_1(\phi)$ y el interior de $Q$ está contenido en $\Pi_2(\phi)$.

El problema de separabilidad geométrica ha atraído recientemente el interés de la comunidad científica, con $\Phi$ considerada regularmente como la familia de lineas, círculos o polígonos simples en el plano.
Si $P$ y $Q$ son conjuntos finitos de puntos en el plano, entonces el problema de separación por líneas se puede resolver usando programación lineal en tiempo $O(n)$~\cite{LinearProgrammingInLinearTime}.

El problema de encontrar un polígono simple separador con el menor número de vértices entre dos conjuntos finitos de puntos fue estudiado por Edelsbrunner y Preparata en~\cite{MinimumPolygonalSeparation}.
Aggarwal, Booth, O'Rourke, Suri y Yap estudiaron el problema de encontrar el polígono separador de área mínima que se encuentra entre las fronteras de dos polígonos convexos anidados~\cite{Aggarwal:1985}.
Das y Joseph extendieron el problema a dimensiones mayores y probaron que el problema de calcular el poliedro separador, que tenga el mínimo número de caras posible, para dos poliedros convexos anidados es NP-completo~\cite{DasJoseph:1990}.

El estudio de la separabilidad por círculos se extendió a partir del descubrimiento de sus muy variadas aplicaciones en el área de reconocimiento de patrones y procesamiento de imagen~\cite{DigitalDiskAndCompacness}~\cite{SeparatingPointsByCricles}.
En dimensiones mayores, Lay~\cite{SeparationBySphericalSurfaces} introdujo la idea de transformar una instancia del problema de separabilidad por esferas en $\mathbb{R}^d$, 
en un problema de separación lineal en $\mathbb{R}^{d+1}$ al utilizar la proyección estereográfica.
Dados $P,Q$ subconjuntos de $\mathbb{R}^2$, el problema de optimización más estudiado es el de encontrar el círculo de radio mínimo que separe a $P$ de $Q$.
Anderson y Kim~\cite{DigitalDiskAndCompacness} presentaron un algoritmo de tiempo cuadrático para resolver este problema entre dos conjuntos finitos de puntos. 
Bhattacharya~\cite{ComputingCircularSeparabilityOfPlanarPointSets} mejoró el tiempo de ejecución a $O(n \log n)$, 
calculando las regiones dónde podrían encontrase centrados todos los posibles círculos  separadores entre ambos conjuntos.
Finalmente Kosaraju, Megiddo y O'Rourke~\cite{ComputingCircularSeparability} propusieron un algoritmo óptimo, 
encontrando en tiempo $O(n)$ el círculo separador de radio mínimo, 
y en tiempo $O(n \log n)$ el círculo separador de radio máximo entre dos conjuntos finitos de puntos. 
Ellos utilizaron transformaciones parabólicas para obtener una instancia de un problema de minimización cuadrática, convexa en tres dimensiones. 
Así mismo Boissonnat, Czyzowicz, Devillers y Yvinec~\cite{CircularSeparabilityOfPolygon} propusieron un algoritmo lineal de decisión, 
que verifica si dos conjuntos de puntos son o no, separables por círculos.

En este trabajo consideramos la versión en línea del problema de separación por círculos, 
en el cual nos permitimos preprocesar un polígono $P$ con $n$ vértices, 
para construir una estructura de datos que soporta consultas de la siguiente forma:

Dado un polígono convexo $Q$ como la lista de sus $m$ vertices, encontrar eficientemente el círculo de radio mínimo que contiene a $P$ y cuyo interior no intersecta a $Q$.
La estructura de datos propuesta en este trabajo requiere de tiempo $O(n)$ para su construcción, utiliza espacio lineal y responde a las consultas en tiempo $O(\log n \log m)$.
Cabe destacar que resolver este problema sin hacer uso del preprocesado requiere de tiempo $O(n)$~\cite{ComputingCircularSeparability}.


